#pragma once
#include<assert.h>

namespace mydeque
{
	template<class inputiterator, class T>
	void fill(inputiterator first, inputiterator last, T val);

	template<class inputiterator, class outputiterator>
	void copy(inputiterator first, inputiterator last, outputiterator dest);
	template<class inputiterator, class outputiterator>
	void copyAtFront(inputiterator first, inputiterator last, outputiterator dest);//从前往后拷贝

	template<class T, class ptr, class ref, size_t bufsize>
	struct deque_iterator {//deque的迭代器
		typedef T* pointer;
		typedef pointer* map_pointer;
		typedef deque_iterator self;

		//constructor
		deque_iterator()
			:first(nullptr), last(nullptr), node(nullptr), cur(nullptr) {
			;
		}
		//function member
		void setnode(map_pointer newnode)
		{
			node = newnode;
			first = *node;
			last = first + bufsize;
		}

		ref operator*() { return *cur; }
		pointer operator->() { return cur; }

		int operator-(const self& x)const
		{
			return int(bufsize * (node - x.node - 1))
				+ cur - first
				+ x.last - x.cur;
		}

		self& operator++() {
			++cur;//访问下一个元素
			if (cur == last) {//如果下一个元素来到了缓冲区的结尾
				setnode(node + 1);//就来到下一个缓冲区
				cur = first;//cur指向新缓冲区的第一个元素
			}
			return *this;
		}

		self operator++(int) {//后置++
			self tmp = *this;
			++(*this);
			return tmp;
		}

		self& operator--() {
			if (cur == first) {//判断cur是否来到了当前缓冲区的起始位置
				setnode(node - 1);//让node跳跃到上一个缓冲区
				cur = last - 1;//让cur指向末尾位置
			}
			else {
				cur--;
			}
			return *this;
		}

		self operator--(int) {//后置--
			self tmp = *this;
			--(*this);
			return tmp;
		}
		//ramdon access function

		self& operator+=(int n)
		{
			int offset = n + (cur - first);
			if (offset >= 0 && offset < bufsize)//判断是否在缓冲区内
			{
				cur += n;
			}
			else//目标不在缓冲区内
			{
				int offset_node =
					offset > 0 ? offset / int(bufsize) : ((offset + 1) / (int)bufsize) - 1;
				setnode(node + offset_node);//切换到正确的缓冲区
				cur = first + offset - offset_node * bufsize;//切换到正确的位置
			}
			return *this;
		}

		self operator+(int n)
		{
			self tmp = *this;
			return tmp += n;
		}

		self& operator-=(int n)
		{
			return *this += (-n);
		}

		self operator-(int n)
		{
			self tmp = *this;
			return tmp -= n;
		}

		ref operator[](int n)
		{
			return *(*this + n);
		}

		bool operator==(const self& x)const
		{
			return cur == x.cur;
		}

		bool operator!=(const self& x)const
		{
			return cur != x.cur;
		}

		bool operator<(const self& x)const
		{
			return node == x.node ? cur < x.cur : node < x.node;
		}
		//data member
		T* first;
		T* last;
		T* cur;
		map_pointer node;
	};

	template<class T, size_t bufsize = 25>//bufsize是deque缓冲区的元素个数
	class deque
	{
	public:
		typedef T* pointer;
		typedef pointer* map_poniter;//中控数组的类型
		typedef deque_iterator<T, T*, T&, bufsize> iterator;//为迭代器起一个别名
		typedef deque_iterator<T, const T*, const T&, bufsize> const_iterator;//为迭代器起一个别名

		deque()
		{
			CreateMapAndNode(0);
		}

		deque(size_t n, T val)
		{
			CreateMapAndNode(n);//生成n个元素的空间
			map_poniter cur;
			for (cur = start.node; cur < finish.node; cur++)
			{
				fill(*cur, *cur + bufsize, val);
			}
			fill(finish.first, finish.last, val);
		}

		//modifier
		void push_back(const T& val)
		{
			if (finish.cur != finish.last - 1)//判断是否来到了缓冲区边界
			{
				*finish = val;
				++finish;
			}
			else {//到达边界，需要开辟新的缓冲区
				ReserveMapAtBack();//判断一下是否需要在map的后端新增缓冲区
				*(finish.node + 1) = new T[bufsize];
				*finish = val;
				finish.setnode(finish.node + 1);
				finish.cur = finish.first;
			}
		}

		void push_front(const T& val)
		{
			if (start.cur != start.first)
			{
				start--;
				*start = val;
			}
			else {
				ReserveMapAtFront();
				*(start.node - 1) = new T[bufsize];
				start--;
				*start = val;
			}
		}

		void pop_back()
		{
			assert(!empty());//空容器不能调用pop_back
			if (finish.cur != finish.first)
			{
				finish--;
			}
			else {
				delete[] finish.first;//释放缓冲区
				finish.setnode(finish.node - 1);
				finish.cur = finish.last - 1;
			}
		}

		void pop_front()
		{
			assert(!empty());
			if (start.cur != start.last - 1)
			{
				start++;
			}
			else
			{
				delete start.first;
				start.setnode(start.node + 1);
				start.cur = start.first;
			}
		}

		void clear()
		{
			for (map_poniter node = start.node; node <= finish.node; ++node)
				delete[] * node;//清除所有缓冲区
			//调整迭代器start和finish
			map_poniter node = map + mapsize / 2;
			*node = new T[bufsize];
			start.setnode(node);
			start.cur = start.first;
			finish = start;

		}

		iterator erase(iterator pos)
		{
			iterator next = pos + 1;
			int index = pos - start;//偏移量
			if (index < size() / 2)
			{
				copyAtFront(start, pos, next);//从前往后拷贝
				pop_front();//删除前面的冗余元素
			}
			else {
				copy(next, finish, pos);//从后向前拷贝
				pop_back();
			}
			return start + index;
		}
		//在pos位置插入一个val元素
		iterator insert(iterator pos, const T& val)
		{
			if (pos.cur == start.cur) {//如果插入在开头，交给push_front
				push_front(val);
				return start;
			}
			else if (pos.cur == finish.cur) {//如果插入在末尾，交个push_back
				push_back(val);
				return finish - 1;
			}
			else {//插入在中间位置
				int index = pos - start;//计算偏移量
				if (index < size() / 2) {
					push_front(front());
					pos = start + index;
					iterator pos1 = pos;
					++pos1;
					copy(start + 2, pos1, start + 1);
				}
				else
				{
					push_back(back());
					pos = start + index;
					copyAtFront(pos, finish - 2, finish - 1);
				}
				*pos = val;
				return pos;
			}
		}

		iterator begin() { return start; }
		iterator end() { return finish; }
		T& front() { return *start; }

		T& back() {
			iterator tmp = finish;
			tmp--;
			return *tmp;
		}

		T& operator[](size_t pos) {
			assert(pos < size());
			return *(start + pos);
		}

		size_t size() { return finish - start; }
		bool empty() { return finish == start; }
	private:
		void CreateMapAndNode(size_t elementNum)
		{
			size_t nodeNum = elementNum / bufsize + 1;//判断待使用的缓冲区有几个
			mapsize = nodeNum < 8 ? 8 : nodeNum + 2;//预留缓冲区，提高效率
			map = new pointer[mapsize];//开辟mapsize个缓冲区

			//计算出[nstart，nfinish]的区间
			map_poniter nstart = map + (mapsize - (elementNum / bufsize)) / 2;
			map_poniter nfinsh = nstart + nodeNum - 1;

			//初始化这个区间
			map_poniter tmp = nstart;
			while (tmp <= nfinsh)
			{
				*tmp = new T[bufsize];//生成缓冲区
				tmp++;
			}
			//初始化迭代器strat和finish，使得这两个迭代器指向deque的起始地址和结尾地址
			start.setnode(nstart);
			finish.setnode(nfinsh);
			start.cur = start.first;
			finish.cur = finish.first + (elementNum % bufsize);
		}

		void ReserveMapAtBack(size_t AddNode = 1)
		{
			if (AddNode >= mapsize - (finish.node - map))
				reallocmap(AddNode, false);
		}

		void ReserveMapAtFront(size_t AddNode = 1)
		{
			if (AddNode >= start.node - map)
				reallocmap(AddNode, true);
		}

		void reallocmap(size_t AddNode, bool AllocAtFront)
		{
			size_t oldnodes = finish.node - start.node + 1;//旧的有效缓冲区个数
			size_t newnodes = oldnodes + AddNode;//新的有效缓冲区个数

			map_poniter newstart;
			size_t newmapsize = mapsize + (mapsize > AddNode ? mapsize : AddNode) + 2;//新map的管理缓冲区个数

			map_poniter newmap = new pointer[newmapsize];//生成新的map数组

			//计算新的迭代器区间
			newstart = newmap + (newmapsize - newnodes) / 2
				+ (AllocAtFront ? AddNode : 0);
			map_poniter newfinish = newstart + oldnodes - 1;

			copy(start.node, finish.node + 1, newstart);//将旧缓冲区交给新的map管理
			delete[] map;//释放旧map
			//更改迭代器以及容器数据
			map = newmap;
			mapsize = newmapsize;
			start.setnode(newstart);
			finish.setnode(newfinish);
		}
		iterator start;//指向数组第一个元素的迭代器
		iterator finish;//指向数组最后一个元素后一位的迭代器
		map_poniter map;//中控数组
		size_t mapsize;//数组的个数


	};

	template<class inputiterator, class outputiterator>
	void copy(inputiterator first, inputiterator last, outputiterator dest)
	{
		while (first != last)
		{
			*dest = *first;
			dest++;
			first++;
		}
	}

	template<class inputiterator, class outputiterator>
	void copyAtFront(inputiterator first, inputiterator last, outputiterator dest)//从后往前拷贝
	{
		while (last != first)
		{
			--last;
			--dest;
			*dest = *last;
		}
	}
	template<class inputiterator, class T>
	void fill(inputiterator first, inputiterator last, T val)
	{
		while (first != last)
		{
			*first = val;
			first++;
		}
	}
}